#删除链表的倒数第N个结点

from typing import Optional


# 定义链表节点（如果环境中没有预定义的话）
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


class Solution:
    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        dummy = ListNode(0, head)  # 虚拟头节点处理边界情况
        fast = slow = dummy

        # 快指针先移动 n+1 步，保持固定间隔
        for _ in range(n):
            if not fast.next:  # 防止 n 超过链表长度
                return head
            fast = fast.next

        # 同步移动直到快指针到末尾
        while fast.next:
            fast = fast.next
            slow = slow.next

        # 删除节点
        slow.next = slow.next.next
        return dummy.next  # 永远返回虚拟节点的下一个




class ListNode:
     def __init__(self, val=0, next=None):
         self.val = val
         self.next = next
class Solution:
    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        dummy = ListNode(0, head)
        fast = slow = dummy

        # 快指针先移动n步
        for _ in range(n):
            fast = fast.next

        # 同时移动，直到快指针到达末尾
        while fast.next:
            fast = fast.next
            slow = slow.next

        # 删除节点
        slow.next = slow.next.next

        return dummy.next